package basic.study.leetcode;

import java.util.HashMap;

/**
 * @ClassName Mid337
 * @Description
 * @Company inspur
 * @Author Kevin
 * @Date 2020/7/26 12:46
 * @Version 1.0
 */
public class Mid337 {
    /**
     * 递归
     */
    class Solution {
        public int rob(TreeNode root) {
            if (root == null) return 0;
            int result = root.val;

            if (root.left != null) {
                result += rob(root.left.left) + rob(root.left.right);
            }
            if (root.right != null) {
                result += rob(root.right.left) + rob(root.right.right);
            }

            return Math.max(rob(root.left)+rob(root.right), result);
        }
    }

    /**
     * dp
     */
    class Solution1 {
        HashMap<TreeNode, Integer> map = new HashMap<>();

        public int rob(TreeNode root) {
            if (root == null) return 0;
            if (map.containsKey(root)) return map.get(root);

            int result = root.val;
            if (root.left != null) {
                result += rob(root.left.left) + rob(root.left.right);
            }
            if (root.right != null) {
                result += rob(root.right.left) + rob(root.right.right);
            }

            result = Math.max(result, rob(root.left)+rob(root.right));
            map.put(root, result);
            return result;
        }
    }

    /**
     * 终极解法
     */
    class Solution2 {
        public int rob(TreeNode root) {
            int[] result = robInternal(root);
            return Math.max(result[0], result[1]);
        }

        private int[] robInternal(TreeNode root) {
            if (root == null) return new int[2];
            int[] result = new int[2];

            int[] left = robInternal(root.left);
            int[] right = robInternal(root.right);

            result[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
            result[1] = left[0] + right[0] + root.val;

            return result;
        }
    }


    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
}
